#ifndef SOLVER_H
#define SOLVER_H

#include "Instance.h"
#include "State.h"

#include <deque>

#include <boost/mpi/communicator.hpp>
#include <boost/mpi/timer.hpp>

namespace mpi = boost::mpi;
using namespace std;

/*
MBG

Metoda:
BB-DFS

Vstup: 
n = prirozene cislo predstavujici pocet uzlu grafu, n ≥ 5
k = prirozene cislo radu jednotek predstavujici stupen uzlu grafu G
G(V,E) = neorietovany neohodnoceny k-regularni graf o n uzlech

Cena:
počet barev
dolni mez = ?			- nevime kolik bude mit optimalni reseni
tesna dolni mez = 2		- urcite to bude vic nez 2
trivialni horni mez = k+1

Hloubka:
n


Sekvencni algoritmus:

Reseni vzdy existuje. Sekvencni algoritmus je typu BB-DFS s omezenou hloubkou prohledavaneho prostoru. Stav je dan castecny obarvenim. Mezistav ci koncovy stav je pripustny, jestlize zadne 2 sousedni uzly nejsou obarvene stejnou barvou. Navrat provadime, pokud nelze zadny uzel pridat, aniz by se porusila podminka barevnosti.

Trivialni horni mez predstavuje obarveni grafu k+1 barvami (kazdy k-regularni graf lze uzlove obarvit k+1 barvami).

Tesna spodni mez je 2. Pokud je G bipartitni, existuje obarveni dvema barvami.

*/

#define CHECK_MSG_AMOUNT  50000

#define MSG_WORK_REQUEST  0           //request more states     ANY => ANY
#define MSG_WORK_SEND     1           //send states             ANY => ANY
#define MSG_WORK_NOWORK   2           //not send states         ANY => ANY
#define MSG_SOLUTION      4           //one who solves the problem sends this to root
#define MSG_TERMINATE     5           //root sends it to everyone, when the solution was found
#define MSG_TOKEN_WHITE   6           //ADUV tokens             ANY => NEI
#define MSG_TOKEN_BLACK   7           //ADUV tokens             ANY => NEI

#define MSG_NONE          8           //dummy for iprobe

#define EX_SOLUTION       0           //solution was found
#define EX_WORK_FINISHED  1           //ADUV end
#define EX_TERMINATE      3           //complete shutdown
#define EX_ERROR          4           //error

#include <boost/archive/text_oarchive.hpp>
#include <boost/archive/text_iarchive.hpp>

#include <boost/serialization/serialization.hpp>
#include <boost/archive/text_iarchive.hpp>
#include <boost/serialization/export.hpp>
#include <boost/serialization/deque.hpp>
#include <boost/serialization/base_object.hpp>

class Stack : public deque<State> {
  private:
    /* BOOST SERIALIZATION */
    friend class boost::serialization::access;
    template<class Archive>
    void serialize(Archive& aAr, const unsigned int version) {
      aAr & boost::serialization::base_object<deque<State> >(*this);
    }

  public:
    Stack split(unsigned int count = 0) {
      Stack kStates;
      if (count == 0) {
        kStates.push_back(this->front());
        this->pop_front();
      } else while(count--) {
        kStates.push_back(this->front());
        this->pop_front();
      }
      return kStates;
    }
};

//BOOST_CLASS_EXPORT_GUID(Stack, "Stack")

class Solver {
  private:
    Stack pStates;           //stack na stavy
    State pState;            //nejlepsi reseni

    mpi::communicator pWorld;//mpi svět
    mpi::timer pTimer;       //mpi timer
    double pElapsed;         //délka výpočtu
 
    long pCounter;           //počet expandovaných stavů
    int pFails;              //počet failnutých žádostí o práci, pro root
    int pNeighbour;          //soused, kterého budeme žádat o práci
    bool pWorkSent;          //v poslední době jsme někomu poslali práci, pro slavy

    int processMessages();
    void incNeighbour();
    void expand();
    void innerLoop();
  public: //lifetime
    Solver();
  public: //own methods
    State getSolution();     //vrátí řešení
    double getElapsed();     //vrátí délku trvání výpočtu
    long getCount();         //vrátí počet expandovaných stavů
    void solve();            //metoda na reseni
};

#endif
// vim: ts=2 fdm=marker syntax=cpp expandtab sw=2
